{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Unicode and Perfect Hashing\n",
    "\n",
    "Generalizing StringZilla from byte-strings to UTF-8 strings requires a deep understanding of Unicode.\n",
    "This notebook is a playground to explore Unicode and UTF-8 encoding.\n",
    "Most importantly it provides a snippet for finding the perfect-hash for unicode, which allows us to produce more efficient histograms and lookup tables for unicode characters.\n",
    "That can be a constituent part of any UTF-8-aware text-processing algorithm, be it Levenshtein automata or distance calculation, Aho-Corasick automata, or high-level NLP tasks, like feature extraction or text classification."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!python -m pip install -q numba numpy tqdm 2>/dev/null || curl -sS https://bootstrap.pypa.io/get-pip.py | python && python -m pip install -q numba numpy tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numba import jit as njit\n",
    "from tqdm import tqdm\n",
    "import numpy as np\n",
    "import random\n",
    "import sys\n",
    "\n",
    "# Import shared Unicode data loading functions\n",
    "sys.path.insert(0, '.')\n",
    "from test_helpers import get_unicode_xml_data, UNICODE_VERSION\n",
    "\n",
    "print(f\"Using Unicode version: {UNICODE_VERSION}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load Unicode XML data (cached)\n",
    "root = get_unicode_xml_data(UNICODE_VERSION)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The XML structure contains a `<repertoire>` element with many `<char>` elements.\n",
    "Each `<char>` element has attributes, including:\n",
    "\n",
    "- `'cp'`: the code point (as hexadecimal)\n",
    "- `'na'`: the character name\n",
    "- `'gc'`: the general category"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Use a namespace-agnostic search for all elements ending with 'char'\n",
    "chars = [elem for elem in root.iter() if elem.tag.endswith('char')]\n",
    "\n",
    "# List to hold all characters (expanded ranges)\n",
    "all_chars = []\n",
    "\n",
    "def process_char(elem):\n",
    "    \"\"\"\n",
    "    Process a <char> element, handling all individual code points (cp)\n",
    "    and ignoring ranges (first-cp and last-cp). Appends each code point to all_chars.\n",
    "    \"\"\"\n",
    "    if 'cp' in elem.attrib:\n",
    "        cp = int(elem.attrib['cp'], 16)\n",
    "        entry = {\n",
    "            'cp': cp,\n",
    "            'name': elem.attrib.get('na', '').strip(),\n",
    "            'gc': elem.attrib.get('gc', '').strip(),\n",
    "            'age': elem.attrib.get('age', '').strip()\n",
    "            # You can add pull attributes here if needed.\n",
    "        }\n",
    "        all_chars.append(entry)\n",
    "\n",
    "# Process every 'char' element found\n",
    "for elem in chars:\n",
    "    process_char(elem)\n",
    "\n",
    "print(f\"Total code points processed (after expanding ranges): {len(all_chars):,}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Unicode standard defines a range of 1,114,112 possible code points (from U+0000 to U+10FFFF), but only a subset of these are actually assigned characters or have specific property data.\n",
    "As of Unicode version 17.0, there are ~160,000 characters with code points, covering 168 modern and historical scripts, as well as multiple symbol sets, split into [338 blocks](https://en.wikipedia.org/wiki/Unicode_block).\n",
    "Let's random sample and print a few:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "random_chars = random.sample(all_chars, 10)\n",
    "\n",
    "print(\"Example symbols:\")\n",
    "for char in random_chars:\n",
    "    cp = char['cp']\n",
    "    na = char['name']\n",
    "    gc = char['gc']\n",
    "    print(f\"U+{cp:04X}: {na} ({gc})\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A natural question can be asked, is that set of codepoints dense or does it contain holes?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "highest_code_point = max(char['cp'] for char in all_chars)\n",
    "print(f\"Highest code point: U+{highest_code_point:04X} ({highest_code_point:,})\")\n",
    "count_holes = highest_code_point - len(all_chars)\n",
    "print(f\"Number of holes: {count_holes:,}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The presence of holes means, that simply using the code-point itself as a lookup index would result in a significant \"memory amplification\" factor, lower data locality, and very uneven distribution of data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "memory_amplification = 1.0 * highest_code_point / len(all_chars)\n",
    "print(f\"Memory amplification: {memory_amplification:.1f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For various hash-functions, we may want to find the smallest buffer size that results in no collisions.\n",
    "Moreover, assuming how small code-points can be, we would prefer hash-functions that only rely on 32-bit arithmetic and avoid expensive operations.\n",
    "We may want to start by using a power-of-two hash-table size, as the final stage of the hash-function can be a simple bitwise-and operation.\n",
    "\n",
    "- $2^{17} = 131072$ is the closes power of two to the number of code-points.\n",
    "- $2^{18} = 262144$ is the next power of two - the first one that fits all code-points.\n",
    "\n",
    "The latter would still have a 69% memory amplifications factor with only 59% of the slots filled."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's export all code-points to a flat NumPy array and for efficiency, calculate all hashes at once."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "code_points = np.array([char['cp'] for char in all_chars], dtype=np.uint32)\n",
    "print(f\"Memory usage for code points: {code_points.nbytes:,} bytes\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ---------------------------------------------------------------------\n",
    "# 1. Jenkins One-at-a-Time Hash\n",
    "# ---------------------------------------------------------------------\n",
    "def hash_all_jenkins(code_points: np.ndarray) -> np.ndarray:\n",
    "    # Ensure input is np.uint32.\n",
    "    code_points = code_points.astype(np.uint32)\n",
    "    h = np.zeros_like(code_points, dtype=np.uint32)\n",
    "    # Process each of the 4 bytes of the 32-bit integer.\n",
    "    for shift in (0, 8, 16, 24):\n",
    "        # Extract one byte at a time.\n",
    "        b = (code_points >> shift) & np.uint32(0xFF)\n",
    "        h = (h + b) & np.uint32(0xFFFFFFFF)\n",
    "        h = (h + (h << np.uint32(10))) & np.uint32(0xFFFFFFFF)\n",
    "        h = (h ^ (h >> np.uint32(6))) & np.uint32(0xFFFFFFFF)\n",
    "    h = (h + (h << np.uint32(3))) & np.uint32(0xFFFFFFFF)\n",
    "    h = (h ^ (h >> np.uint32(11))) & np.uint32(0xFFFFFFFF)\n",
    "    h = (h + (h << np.uint32(15))) & np.uint32(0xFFFFFFFF)\n",
    "    return h\n",
    "\n",
    "# ---------------------------------------------------------------------\n",
    "# 2. FNV-1a Hash (32-bit)\n",
    "# ---------------------------------------------------------------------\n",
    "def hash_all_fnv1a(code_points: np.ndarray) -> np.ndarray:\n",
    "    # FNV-1a 32-bit parameters\n",
    "    FNV_offset = np.uint32(0x811C9DC5)\n",
    "    FNV_prime  = np.uint32(16777619)\n",
    "    code_points = code_points.astype(np.uint32)\n",
    "    h = np.full_like(code_points, FNV_offset, dtype=np.uint32)\n",
    "    # Process each of the 4 bytes\n",
    "    for shift in (0, 8, 16, 24):\n",
    "        byte = (code_points >> shift) & np.uint32(0xFF)\n",
    "        h = h ^ byte\n",
    "        h = (h * FNV_prime) & np.uint32(0xFFFFFFFF)\n",
    "    return h\n",
    "\n",
    "# ---------------------------------------------------------------------\n",
    "# 3. Thomas Wang's 32-bit Integer Hash\n",
    "# ---------------------------------------------------------------------\n",
    "def hash_all_thomas_wang(code_points: np.ndarray) -> np.ndarray:\n",
    "    code_points = code_points.astype(np.uint32)\n",
    "    x = code_points.copy()\n",
    "    x = (x ^ np.uint32(61)) ^ (x >> np.uint32(16))\n",
    "    x = (x + (x << np.uint32(3))) & np.uint32(0xFFFFFFFF)\n",
    "    x = x ^ (x >> np.uint32(4))\n",
    "    x = (x * np.uint32(0x27d4eb2d)) & np.uint32(0xFFFFFFFF)\n",
    "    x = x ^ (x >> np.uint32(15))\n",
    "    return x\n",
    "\n",
    "# ---------------------------------------------------------------------\n",
    "# 4. MurmurHash3 (x86 32-bit variant for 4-byte input)\n",
    "# ---------------------------------------------------------------------\n",
    "def hash_all_murmur3(code_points: np.ndarray, seed: np.uint32 = np.uint32(0)) -> np.ndarray:\n",
    "    code_points = code_points.astype(np.uint32)\n",
    "    c1 = np.uint32(0xcc9e2d51)\n",
    "    c2 = np.uint32(0x1b873593)\n",
    "    r1 = np.uint32(15)\n",
    "    r2 = np.uint32(13)\n",
    "    m  = np.uint32(5)\n",
    "    n  = np.uint32(0xe6546b64)\n",
    "    \n",
    "    # Treat each 32-bit integer as 4 bytes of data.\n",
    "    k = (code_points * c1) & np.uint32(0xFFFFFFFF)\n",
    "    k = ((k << r1) | (k >> (32 - r1))) & np.uint32(0xFFFFFFFF)\n",
    "    k = (k * c2) & np.uint32(0xFFFFFFFF)\n",
    "    \n",
    "    h = seed ^ k\n",
    "    h = ((h << r2) | (h >> (32 - r2))) & np.uint32(0xFFFFFFFF)\n",
    "    h = (h * m + n) & np.uint32(0xFFFFFFFF)\n",
    "    \n",
    "    # Since input length is always 4 bytes for a 32-bit integer:\n",
    "    h ^= np.uint32(4)\n",
    "    # Finalization mix\n",
    "    h ^= (h >> np.uint32(16))\n",
    "    h = (h * np.uint32(0x85ebca6b)) & np.uint32(0xFFFFFFFF)\n",
    "    h ^= (h >> np.uint32(13))\n",
    "    h = (h * np.uint32(0xc2b2ae35)) & np.uint32(0xFFFFFFFF)\n",
    "    h ^= (h >> np.uint32(16))\n",
    "    return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_unique(x: np.ndarray) -> int:\n",
    "    # This approach is about 50% faster than `len(np.unique(x))`.\n",
    "    if x.size == 0:\n",
    "        return 0\n",
    "    xs = np.sort(x)\n",
    "    return int(np.count_nonzero(np.diff(xs)) + 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def rotate_left(x: np.ndarray, r: int) -> np.ndarray:\n",
    "    \"\"\"Rotate left the 32-bit integers in x by r bits.\"\"\"\n",
    "    return ((x << np.uint32(r)) | (x >> np.uint32(32 - r))) & np.uint32(0xFFFFFFFF)\n",
    "\n",
    "def hash_custom(code_points: np.ndarray) -> np.ndarray:\n",
    "    \"\"\"\n",
    "    Compute a composite hash on an array of 32-bit integers.\n",
    "    The hash is a combination of multiplications, rotations, and XOR mixing.\n",
    "    \"\"\"\n",
    "    # Ensure code_points are treated as 32-bit unsigned integers.\n",
    "    x = code_points.astype(np.uint32)\n",
    "    \n",
    "    # First mixing stage:\n",
    "    # Multiply by a constant and then rotate left.\n",
    "    x = (x * np.uint32(0xcc9e2d51)) & np.uint32(0xFFFFFFFF)\n",
    "    x = rotate_left(x, 15)\n",
    "    \n",
    "    # Second stage: XOR with a constant.\n",
    "    x ^= np.uint32(0x1b873593)\n",
    "    \n",
    "    # Third stage: Multiply and then rotate.\n",
    "    x = (x * np.uint32(0x85ebca6b)) & np.uint32(0xFFFFFFFF)\n",
    "    x = rotate_left(x, 13)\n",
    "    \n",
    "    # Fourth stage: Final XOR mix.\n",
    "    x ^= np.uint32(0xc2b2ae35)\n",
    "    \n",
    "    # Optionally, perform one more multiplication to scramble bits further.\n",
    "    x = (x * np.uint32(0x27d4eb2d)) & np.uint32(0xFFFFFFFF)\n",
    "    \n",
    "    return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for name, func in [\n",
    "    ('Jenkins One-at-a-Time', hash_all_jenkins),\n",
    "    ('FNV-1a', hash_all_fnv1a),\n",
    "    (\"Thomas Wang's Hash\", hash_all_thomas_wang),\n",
    "    ('MurmurHash3', hash_all_murmur3),\n",
    "    ('Custom', hash_custom),\n",
    "]:\n",
    "    print(f\"\\n{name}:\")\n",
    "    hashes = func(code_points)\n",
    "    \n",
    "    unique_hashes = count_unique(hashes)\n",
    "    print(f\"Unique hashes: {unique_hashes:,} = {unique_hashes / len(code_points):.4%}\")\n",
    "    \n",
    "    # Lets estimate the number of collisions for different modulo values\n",
    "    hashes_modulo_valid = hashes % len(code_points)\n",
    "    unique_hashes_modulo_valid = count_unique(hashes_modulo_valid)\n",
    "    print(f\"Unique hashes (modulo size): {unique_hashes_modulo_valid:,} = {unique_hashes_modulo_valid / len(code_points):.4%}\")\n",
    "    \n",
    "    # Try the next power of 2 for modulo size\n",
    "    bitceil = 2 ** 18\n",
    "    hashes_modulo_bitceil = hashes % bitceil\n",
    "    unique_hashes_modulo_bitceil = count_unique(hashes_modulo_bitceil)\n",
    "    print(f\"Unique hashes (modulo {bitceil}): {unique_hashes_modulo_bitceil:,} = {unique_hashes_modulo_bitceil / len(code_points):.4%}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We end up with a fairly high collision rate of around 37% with vocabulary-size modulo and slightly more tolerable 25% with the next power of two.\n",
    "Still, that's far from perfect-hashing.\n",
    "Let's try different multiplicative hash-functions and see if we can find a better one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Take the range of all 32-bit unsigned integers\n",
    "# ? Random shuffling to simplify the search for the first multiplier is a good idea,\n",
    "# ? but it would take forever to run on 4 billion elements in Python.\n",
    "# ! all_integers = np.arange(1, 2**32, dtype=np.uint32)\n",
    "# ! np.random.shuffle(all_integers)\n",
    "all_integers = np.random.permutation(2**32)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "all_integers = all_integers.astype(np.uint32)\n",
    "print(f\"Memory usage for all_integers: {all_integers.nbytes:,} bytes\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Take the range of all 32-bit unsigned integers\n",
    "bitceil = 2 ** 18\n",
    "for multiplier in tqdm(all_integers):\n",
    "    hashes = code_points * multiplier\n",
    "    \n",
    "    # Lets estimate the number of collisions for different modulo values\n",
    "    hashes_modulo_valid = hashes % len(code_points)\n",
    "    unique_hashes_modulo_valid = count_unique(hashes_modulo_valid)\n",
    "    if unique_hashes_modulo_valid == len(code_points):\n",
    "        print(f\"Multiplier (modulo size): {multiplier}\")\n",
    "        break\n",
    "    \n",
    "    # Try the next power of 2 for modulo size\n",
    "    hashes_modulo_bitceil = hashes % bitceil\n",
    "    unique_hashes_modulo_bitceil = count_unique(hashes_modulo_bitceil)\n",
    "    if unique_hashes_modulo_bitceil == len(code_points):\n",
    "        print(f\"Multiplier (modulo {bitceil}): {multiplier}\")\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from numba import uint32\n",
    "\n",
    "@njit(nopython=True)\n",
    "def check_multiplier(code_points: np.ndarray, multiplier: uint32, seen_flags: np.ndarray) -> bool:\n",
    "    \"\"\"\n",
    "    Check if the multiplier produces a perfect hash mapping\n",
    "    for the given code_points with modulus `len(seen_flags)`.\n",
    "    Returns True if no collisions are found, False otherwise.\n",
    "    \"\"\"\n",
    "    # Create an array of flags for each hash value.\n",
    "    n = code_points.shape[0]\n",
    "    modulo = uint32(len(seen_flags))\n",
    "    for i in range(n):\n",
    "        # Compute hash value (simulate 32-bit wrap-around implicitly via modulo arithmetic)\n",
    "        h = uint32(code_points[i] * multiplier) % modulo\n",
    "        if seen_flags[h] == 1:\n",
    "            # Collision found.\n",
    "            return False\n",
    "        seen_flags[h] = 1\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Take the range of all 32-bit unsigned integers\n",
    "seen_modulo_vocabulary = np.zeros(len(code_points), dtype=np.uint8)\n",
    "seen_modulo_bitceil = np.zeros(2 ** 18, dtype=np.uint8)\n",
    "\n",
    "for multiplier in tqdm(all_integers):\n",
    "    seen_modulo_vocabulary.fill(0)\n",
    "    seen_modulo_bitceil.fill(0)\n",
    "\n",
    "    # Lets estimate the number of collisions for different modulo values\n",
    "    if check_multiplier(code_points, multiplier, seen_modulo_vocabulary):\n",
    "        print(f\"Multiplier (modulo size): {multiplier}\")\n",
    "        break\n",
    "\n",
    "    if check_multiplier(code_points, multiplier, seen_modulo_bitceil):\n",
    "        print(f\"Multiplier (modulo {bitceil}): {multiplier}\")\n",
    "        break"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "StringZilla",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
